//
// Created by user on 2022/4/25.
//

#include <vector>
using namespace std;
/*
 多重背包：
有n种物品和一个容量为C的背包第i种物品的重量是wW[i]，价值是V[i]，件数是p[i】
求将哪些物品装入背包可使得价值总和最大
 */
#include <vector>
#include <algorithm>
using namespace std;
class MultipleKnapsack{
public:
    int multipleknapsack(vector<int> &w, vector<int> &v, vector<int> &p, int C){
//定义维度
        vector<vector<int>> dp(w.size(), vector<int>(C+1));

        //初始化
        for (int c = 0; c <= C; ++c) {
            dp[0][c] = (c/w[0])*v[0];
        }

        for (int i = 1; i <w.size() ; ++i) {
            for (int j = 0; j <=C ; ++j) {
                int count = min(j/w[i], p[i]);
                for (int k = 0; k <=count ; ++k) {
                    dp[i][j] = max(dp[i][j], k*v[i]+dp[i-1][j-k*w[i]]);
                }
            }
        }
        return dp[w.size()-1][C];
    }
};
